<html>
<head><meta charset="utf-8"><title>dictionary passing project · t-compiler/wg-polymorphization · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/index.html">t-compiler/wg-polymorphization</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/dictionary.20passing.20project.html">dictionary passing project</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="210490670"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/dictionary%20passing%20project/near/210490670" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> sfzhu <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/dictionary.20passing.20project.html#210490670">(Sep 18 2020 at 08:21)</a>:</h4>
<p>Hello all,</p>
<p>Great to know this channel from <span class="user-mention" data-user-id="116107">@davidtwco</span> ! I am Shuofei Zhu from Penn State and working on the project exploring dictionary-passing style for generics. My understanding for "dictionary-passing" is similar to using a vtable for dynamic dispatch. I think what we are going to do is kind of like making some of the functions with type parameters to be dynamically dispatched.</p>
<div class="codehilite"><pre><span></span><code><span class="k">fn</span> <span class="nf">add_test</span><span class="o">&lt;</span><span class="n">T</span><span class="o">&gt;</span><span class="p">(</span><span class="n">a</span>: <span class="nc">T</span><span class="p">,</span><span class="w"> </span><span class="n">b</span>: <span class="nc">T</span><span class="p">)</span><span class="w"> </span>-&gt; <span class="nc">T</span><span class="w"> </span><span class="k">where</span><span class="w"> </span><span class="n">T</span>: <span class="nc">Add</span><span class="o">&lt;</span><span class="n">Output</span><span class="o">=</span><span class="n">T</span><span class="o">&gt;</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">   </span><span class="kd">let</span><span class="w"> </span><span class="n">c</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="n">b</span><span class="p">;</span><span class="w"></span>
<span class="w">   </span><span class="n">c</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>

<span class="k">fn</span> <span class="nf">myprint</span><span class="o">&lt;</span><span class="n">T</span>: <span class="nc">std</span>::<span class="n">fmt</span>::<span class="n">Display</span><span class="o">&gt;</span><span class="p">(</span><span class="n">x</span>: <span class="nc">T</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">   </span><span class="n">println</span><span class="o">!</span><span class="p">(</span><span class="s">&quot;{}&quot;</span><span class="p">,</span><span class="w"> </span><span class="n">x</span><span class="p">);</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>

<span class="k">fn</span> <span class="nf">main</span><span class="p">()</span><span class="w"> </span><span class="p">{</span><span class="w"></span>

<span class="w">   </span><span class="kd">let</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">add_test</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span><span class="w"> </span><span class="mi">2</span><span class="p">);</span><span class="c1">//i32</span>
<span class="w">   </span><span class="kd">let</span><span class="w"> </span><span class="n">b</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">add_test</span><span class="p">(</span><span class="mf">1.0</span><span class="p">,</span><span class="w"> </span><span class="mf">2.0</span><span class="p">);</span><span class="c1">//f64</span>

<span class="w">   </span><span class="n">myprint</span><span class="p">(</span><span class="n">a</span><span class="p">);</span><span class="w"></span>
<span class="w">   </span><span class="n">myprint</span><span class="p">(</span><span class="n">b</span><span class="p">);</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>
</code></pre></div>


<p>For the above code, hopefully it would be compiled to some LLVM code similar to the following ones:</p>
<div class="codehilite"><pre><span></span><code>@vtable.i32 = {null, size:32, null, add_func_i32}
@vtable.f64 = {null, size:32, null, add_func_f64}

add_func_int(a: *i32, b: *i32) -&gt; *i32 {
   ai=  Load a;
   bi = load b;
   return Box::new(add());
}

fn add_test(a: *Add, b: *Add, vtable: VtableOfAdd) -&gt; *Add {
   Add_func = vtable[3]
   c = add_func(a, b)
   c
}

fn myprint&lt;T: std::fmt::Display&gt;(x: T) {
   println!(&quot;{}&quot;, x);
}

fn main() {

   let a = add_test(1, 2, @vtable.i32);//i32
   let b = add_test(1.0, 2.0, @vtable.i64);//f64

   myprint(a);
   myprint(b);
}
</code></pre></div>


<p>As <code>std::ops::Add</code> has been implemented for i32 and f64, we only change how <code>add_test</code> is compiled. (I guess the criterion is universal types vs existential types). <br>
I would like to ask about the implementation. I found Rust already has <code>dyn trait</code>s to implement dynamic dispatch with a vtable. One way to implement dictionary passing is to change the codegen part by reusing some code from <code>dyn trait</code>s to generate similar LLVM code. </p>
<p>But I am not sure if there’s another way: change the MIR or HIR at some stage, and turn the type parameters into <code>dyn trait</code>s, so that they are compiled as <code>dyn trait</code>s naturally? Since using type parameters makes more constraints than using traits only, I think at some stage (e.g. after type checking), the type parameters could be substituted to <code>dyn trait</code>s while keeping the semantics.</p>
<p>To me, the second way sounds promising, but I am not sure if my understanding is correct. If so, should I change HIR or MIR, and after which analyses (e.g., type checking)?</p>
<p>Thanks,<br>
Shuofei</p>



<a name="210819169"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/dictionary%20passing%20project/near/210819169" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/dictionary.20passing.20project.html#210819169">(Sep 22 2020 at 01:07)</a>:</h4>
<p>I have no idea how this can be made to work in most cases, <code>rustc</code> relies heavily on knowing what generics expand to</p>



<a name="210819228"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/dictionary%20passing%20project/near/210819228" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/dictionary.20passing.20project.html#210819228">(Sep 22 2020 at 01:08)</a>:</h4>
<p>your <code>add_test</code> example is impossible to write with <code>dyn Trait</code> because you can write <code>dyn Add&lt;Output = i32&gt;</code> but you can't avoid specifying the associated type, as the typesystem still reasons about it statically</p>



<a name="210819259"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/dictionary%20passing%20project/near/210819259" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/dictionary.20passing.20project.html#210819259">(Sep 22 2020 at 01:09)</a>:</h4>
<p><code>dyn Trait</code> only injects one existential variable into the "ambient" indirection (I really wish I got around to writing the spec for this, it's a really fascinating topic)</p>



<a name="210819329"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/dictionary%20passing%20project/near/210819329" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/dictionary.20passing.20project.html#210819329">(Sep 22 2020 at 01:10)</a>:</h4>
<p>even if you pick traits without associated types, you still could only handle a single value of that type with <code>dyn Trait</code></p>



<a name="210819350"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/dictionary%20passing%20project/near/210819350" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/dictionary.20passing.20project.html#210819350">(Sep 22 2020 at 01:10)</a>:</h4>
<p>because of lifetimes, it's <em>fundamentally impossible</em> to check/ensure that two arbitrary values of some <code>dyn Trait</code> are the same type</p>



<a name="210819392"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/dictionary%20passing%20project/near/210819392" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/dictionary.20passing.20project.html#210819392">(Sep 22 2020 at 01:11)</a>:</h4>
<p>so overall what this means is you would have to carry the existential/universal logic pretty far down, and couldn't reuse <code>dyn Trait</code> except for cases when the user can write <code>dyn Trait</code> today (I suggest trying, it's hard to come up with non-trivial examples)</p>



<a name="210819463"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/dictionary%20passing%20project/near/210819463" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/dictionary.20passing.20project.html#210819463">(Sep 22 2020 at 01:13)</a>:</h4>
<p>also, the HIR is immutable, so at most you could transform MIR, but the mutable part of MIR is just the "body" of a function (or compile-time initializer but that's not relevant here)</p>



<a name="210819494"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/dictionary%20passing%20project/near/210819494" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/dictionary.20passing.20project.html#210819494">(Sep 22 2020 at 01:14)</a>:</h4>
<p>once they have been lowered from AST to HIR and then from the HIR to the typesystem, you can't transform the signature or generics of a definition</p>



<a name="210819561"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/dictionary%20passing%20project/near/210819561" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/dictionary.20passing.20project.html#210819561">(Sep 22 2020 at 01:14)</a>:</h4>
<p>(this is by design, <code>rustc</code> largely doesn't operate in "passes", but rather a more fluid dependency graph - so if you were able to modify something, you could invalidate a previous observation)</p>



<a name="210820430"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/dictionary%20passing%20project/near/210820430" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/dictionary.20passing.20project.html#210820430">(Sep 22 2020 at 01:33)</a>:</h4>
<p><span class="user-mention" data-user-id="343499">@Shuofei Zhu</span> my suggestion would be to do something similar to <span class="user-mention" data-user-id="116107">@davidtwco</span>'s "polymorphization":</p>
<ol>
<li>
<p>you'd have an analysis on the MIR which checks that type parameters are only used in restricted ways</p>
<ul>
<li>it can call methods of traits that are in your own bounds, but <em>not</em> other functions with the same bounds, as there is no guarantee they will also succeed this analysis (unless you want to make it transitive which is harder)</li>
<li>you also can't allow creating derived types like <code>Option&lt;T&gt;</code>, because computing the layout of that at runtime is untractable</li>
<li><del>your <code>add_test</code> example would still not be allowed because it returns a value of an unknown size, which is not something physically possible without auto-boxing or LLVM changes to allow a fancy stack juggling ABI (I can go into more details if you're curious)</del></li>
<li>actually, I think we can make <code>add_test</code> work because unlike <code>dyn Trait</code>, the caller <em>knows</em> the size (since it corresponds to what would've been a generic param) and can create an appropriately-sized stack slot for it</li>
</ul>
</li>
<li>
<p>you'd tweak codegen to handle "dynamicized" generics:</p>
<ul>
<li>to not break everything working with values and expecting to be able to do e.g. <code>size_of_val</code>, you'd have to replace every type parameter <code>T</code> with <code>dyn DynGeneric&lt;T&gt;</code> (new empty trait, special for this), and combine some vtables with stack slot pointers to create pseudo-trait objects</li>
<li>when handling calls involving generics, I think the easiest way is letting the trait system resolve <code>&lt;dyn DynGeneric&lt;T&gt; as Trait&gt;::method</code> as a special kind of "virtual call" (or I guess you could try to intercept <code>dyn DynGeneric&lt;T&gt;</code> before it ever gets there), that you then implement by getting the method from the right vtable (as opposed to from one of the arguments)</li>
</ul>
</li>
</ol>



<a name="210820505"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/dictionary%20passing%20project/near/210820505" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/dictionary.20passing.20project.html#210820505">(Sep 22 2020 at 01:35)</a>:</h4>
<p>this is where virtual calls are handled today <a href="https://github.com/rust-lang/rust/blob/f47df31ae5d7d9795399dca3a0003c1856900361/compiler/rustc_codegen_ssa/src/mir/block.rs#L724-L770">https://github.com/rust-lang/rust/blob/f47df31ae5d7d9795399dca3a0003c1856900361/compiler/rustc_codegen_ssa/src/mir/block.rs#L724-L770</a></p>



<a name="210820585"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/dictionary%20passing%20project/near/210820585" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/dictionary.20passing.20project.html#210820585">(Sep 22 2020 at 01:36)</a>:</h4>
<p><span class="user-mention" data-user-id="343499">@Shuofei Zhu</span> while it might seem plausible to do some of these transformations on the MIR itself, I don't think you can encode enough easily in MIR today</p>



<a name="210820742"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/dictionary%20passing%20project/near/210820742" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/dictionary.20passing.20project.html#210820742">(Sep 22 2020 at 01:40)</a>:</h4>
<p>I guess there's that and also the fact that MIR semantics shouldn't be affected by the choice of codegen strategy: if something is compatible with the dynamic approach then it's "just" another low-level representation (below MIR)</p>



<a name="210820756"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/dictionary%20passing%20project/near/210820756" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/dictionary.20passing.20project.html#210820756">(Sep 22 2020 at 01:41)</a>:</h4>
<p>at most you end up with a precomputed list of vtables to pass to the function and a bitset of "dynamicized" generic parameters</p>



<a name="210820821"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/dictionary%20passing%20project/near/210820821" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/dictionary.20passing.20project.html#210820821">(Sep 22 2020 at 01:42)</a>:</h4>
<p>the other thing I wanted to mention is that this is similar to <span class="user-mention" data-user-id="116009">@nikomatsakis</span>' ideas about an explicit <code>fn foo&lt;dyn T: ...&gt;</code> syntax, which is statically type-checked (and all of the conditions I mentioned above are enforced) but compiled to the dictionary-passing style</p>



<a name="210820872"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/dictionary%20passing%20project/near/210820872" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/dictionary.20passing.20project.html#210820872">(Sep 22 2020 at 01:44)</a>:</h4>
<p>the best-effort vs explicit cases could share most of the code, I think - all of the codegen logic would probably be the same, it's just the checks that would result in user-facing errors only for the <code>dyn T</code> feature</p>



<a name="210820901"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/dictionary%20passing%20project/near/210820901" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/dictionary.20passing.20project.html#210820901">(Sep 22 2020 at 01:44)</a>:</h4>
<p>but anyway yeah this would be more limited than e.g. Swift generics, which can be made dynamic to pretty much any extent</p>



<a name="211093768"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/dictionary%20passing%20project/near/211093768" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> sfzhu <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/dictionary.20passing.20project.html#211093768">(Sep 24 2020 at 06:26)</a>:</h4>
<p>Thank you so much about your advice! <br>
I am sorry I didn't make it clear, but briefly, I think what we would like to do <em>is</em> <code>fn foo&lt;dyn T: ...&gt;</code>. My understanding was like this: rust has a strict typing constraint system, but once a piece of code passes those checkings (traits, associated types, etc), the compiler still has a choice to make it statically or dynamically dispatched (the latter could also be called dictionary-passing style). </p>
<p>We can have a table like this:<br>
|         | use constraints           | no constraints  |<br>
| ------------- |-------------| -----|<br>
| static dispatch      | <code>fn foo&lt;T: Trait&gt;</code> | (not sure) |<br>
| dynamic dispatch      |   <code>fn foo&lt;dyn T: Trait&gt;</code>    |  <code>fn foo(t: &amp;dyn Trait)</code> |</p>



<a name="211097310"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/dictionary%20passing%20project/near/211097310" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> sfzhu <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/dictionary.20passing.20project.html#211097310">(Sep 24 2020 at 07:29)</a>:</h4>
<p>don't know why cannot edit the table anymore, but remake the table as below:</p>
<table>
<thead>
<tr>
<th>dispatch</th>
<th>use constraints</th>
<th>no constraints</th>
</tr>
</thead>
<tbody>
<tr>
<td>static dispatch</td>
<td><code>fn foo&lt;T: Trait&gt;</code></td>
<td>(not sure)</td>
</tr>
<tr>
<td>dynamic dispatch</td>
<td><code>fn foo&lt;dyn T: Trait&gt;</code></td>
<td><code>fn foo(t: &amp;dyn Trait)</code></td>
</tr>
</tbody>
</table>



<a name="211098131"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/dictionary%20passing%20project/near/211098131" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> sfzhu <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/dictionary.20passing.20project.html#211098131">(Sep 24 2020 at 07:40)</a>:</h4>
<p>So right now, as a research project, we are trying to implement a prototype in a short time and do some performance test (e.g., how much code debloated, how much <del>compliation time saved</del>runtime overhead introduced...). We would like to compile as much generic code (<code>fn foo&lt;T: ...&gt;</code>s) as we can, into a dictionary-passing style.  After getting some conclusions from the experiment, we may furthermore implement a <code>fn foo&lt;dyn T: ...&gt;</code> feature with dictionary-passing in a decent way. <br>
So my question should be: what would be an easier way to implement it: after the type checkings, compile the generics into vtables, by a) changing the types into <code>&amp;dyn trait</code>s to make it generate vtables, or b) change the codegen part and do some extra things during codegen?</p>



<a name="211099497"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/dictionary%20passing%20project/near/211099497" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> sfzhu <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/dictionary.20passing.20project.html#211099497">(Sep 24 2020 at 07:58)</a>:</h4>
<p>From what you introduced to me, I feel like method a) may be hard to implement. It requires some large changes on existing HIR/MIR structures. Even though we can do the type checks first then change them to dynamic, changing the structures would also be complex. Currently, we are working on method b). We may not be able to elegantly reuse existing trait &amp; vtable implementations, but will try to generate LLVM code that is close to existing implementations.</p>



<a name="211100186"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/dictionary%20passing%20project/near/211100186" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> sfzhu <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/dictionary.20passing.20project.html#211100186">(Sep 24 2020 at 08:06)</a>:</h4>
<p>Some more details of method b) we are considering:</p>
<ol>
<li>You mentioned "we can make <code>add_test</code> work" because "the caller knows the size". But that was still a bit hard to generate a proper llvm code. We decide to make a wrapper of the <code>impl</code>s of <code>Add</code> on different types, i.e. </li>
</ol>
<div class="codehilite"><pre><span></span><code>add_func_int(a: *i32, b: *i32) -&gt; *i32 {
   ai=  Load a;
   bi = load b;
   return Box::new(std::op::Add(ai, bi));
}
</code></pre></div>


<ol start="2">
<li>We'd like to convert one of the instances of <code>add_test</code> into one with dynamic trait parameters, and remove the redundant instances. We noticed that a <code>dyn trait</code> would be compiled into actually two parameters in LLVM: one is like a <code>void *</code> pointer in C (<code>{}*</code>) to pass the data, the other is a vtable. At the callsite of <code>add_test</code>, the vtable was passed in as a parameter, which is basically what my example shows. </li>
<li>At the stage of codegen, I think the trait information of <code>T:Add</code> has lost, so we may do some analyses again on MIR to make the vtables. This could be some redundant work, as trait information of them was computed earlier. But for a quick prototype, it may not be that bad.</li>
</ol>



<a name="211100368"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/dictionary%20passing%20project/near/211100368" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> sfzhu <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/dictionary.20passing.20project.html#211100368">(Sep 24 2020 at 08:08)</a>:</h4>
<p>Right now, I am finding out how I can make step 2. I may have to build a trait (<code>ty::Dynamic</code>), as it seems to be the only <code>TyKind</code> to make a <code>{}*</code>.</p>



<a name="211101815"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/dictionary%20passing%20project/near/211101815" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> sfzhu <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/dictionary.20passing.20project.html#211101815">(Sep 24 2020 at 08:24)</a>:</h4>
<p>One more detail: I think most data would be passed through a void pointer, as what we would do in <code>&amp;dyn Trait</code>.</p>



<a name="211114430"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/dictionary%20passing%20project/near/211114430" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> davidtwco <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/dictionary.20passing.20project.html#211114430">(Sep 24 2020 at 10:47)</a>:</h4>
<p>cc <span class="user-mention" data-user-id="119009">@eddyb</span></p>



<a name="211924630"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/dictionary%20passing%20project/near/211924630" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/dictionary.20passing.20project.html#211924630">(Oct 01 2020 at 15:07)</a>:</h4>
<p><span class="user-mention" data-user-id="343499">@Shuofei Zhu</span> I don't think this would be a short-term project. sadly I am quite busy lately so I'm not sure how much I could help</p>



<a name="211924663"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/dictionary%20passing%20project/near/211924663" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/dictionary.20passing.20project.html#211924663">(Oct 01 2020 at 15:07)</a>:</h4>
<p>returning <code>Box</code> isn't necessary because you can have the function take a "return pointer"</p>



<a name="211924736"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/dictionary%20passing%20project/near/211924736" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/dictionary.20passing.20project.html#211924736">(Oct 01 2020 at 15:08)</a>:</h4>
<p>things like large structs are "returned" by passing in a pointer to write the return value to</p>



<a name="211924829"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/dictionary%20passing%20project/near/211924829" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/dictionary.20passing.20project.html#211924829">(Oct 01 2020 at 15:08)</a>:</h4>
<p>if you make all functions with an unknown-size-return use that feature, it should "just work", as the caller can correctly allocate the right stack slot size</p>



<a name="211924896"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/dictionary%20passing%20project/near/211924896" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/dictionary.20passing.20project.html#211924896">(Oct 01 2020 at 15:09)</a>:</h4>
<p>with <code>-&gt; dyn Trait</code> this is impossible because the caller doesn't know ahead of time <em>which type</em> you may have chosen</p>



<a name="211924944"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/dictionary%20passing%20project/near/211924944" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/dictionary.20passing.20project.html#211924944">(Oct 01 2020 at 15:09)</a>:</h4>
<p>but with <code>-&gt; T</code>, it knows it's whatever <code>T</code> is (whether static or can dynamically get the size from the vtable)</p>



<a name="212003580"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/dictionary%20passing%20project/near/212003580" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> sfzhu <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/dictionary.20passing.20project.html#212003580">(Oct 02 2020 at 04:22)</a>:</h4>
<p>Already many thanks! I will ask some detailed technical questions in t-compiler/help or other streams in the future.</p>



<a name="213355961"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/dictionary%20passing%20project/near/213355961" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> sfzhu <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/dictionary.20passing.20project.html#213355961">(Oct 14 2020 at 22:03)</a>:</h4>
<p><span class="user-mention" data-user-id="119009">@eddyb</span> <span class="user-mention" data-user-id="116107">@davidtwco</span>  One quick question I have been looking for and asking: how can I make a wrapper function for add? I am not sure which part of rustc I can refer to, so that I can write some llvm code directly, as well as insert a function into the existing function list.</p>



<a name="213677319"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/dictionary%20passing%20project/near/213677319" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> sfzhu <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/dictionary.20passing.20project.html#213677319">(Oct 17 2020 at 23:58)</a>:</h4>
<p>never mind, I have figured it out.</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>